#include <bits/stdc++.h>
using namespace std;

/*
37. 解数独
已解答
困难
相关标签
premium lock icon
相关企业
编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

 

示例 1：


输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：


 

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
*/

// 法一
class Solution {
public:
    /**
     * 检查在棋盘的(x,y)位置填入字符c是否合法（符合数独规则）
     * 数独规则：同一行、同一列、同一3x3子格中不能有重复数字
     * @param board 待检查的数独棋盘
     * @param x 当前位置的行索引
     * @param y 当前位置的列索引
     * @param c 待填入的数字字符（'1'-'9'）
     * @return 合法返回true，否则返回false
     */
    bool isValid(vector<vector<char>>& board, int x, int y, char c){
        // 1. 检查当前列（y列）是否已有c：遍历所有行，列固定为y
        for(int i = 0; i < 9; i++){
            if(board[i][y] == c)
                return false;
        }
        // 2. 检查当前行（x行）是否已有c：遍历所有列，行固定为x
        for(int i = 0; i < 9; i++){
            if(board[x][i] == c)
                return false;
        }
        // 3. 检查当前位置所在的3x3子格是否已有c
        // 计算3x3子格的起始行：x//3得到子格所在行块（0-2），乘以3得到起始行索引
        int startRow = (x / 3) * 3;
        // 计算3x3子格的起始列：y//3得到子格所在列块（0-2），乘以3得到起始列索引
        int startCol = (y / 3) * 3;
        // 遍历当前3x3子格的所有9个位置
        for(int i = startRow; i < startRow + 3; i++){
            for(int j = startCol; j < startCol + 3; j++){
                if(board[i][j] == c)
                    return false;
            }
        }
        // 所有检查通过，填入c合法
        return true;
    }

    /**
     * 递归回溯求解数独
     * 核心逻辑：找到空位置（.）→ 尝试填入合法数字 → 递归求解 → 求解成功返回true，失败则回溯（恢复空位置）
     * @param board 待求解的数独棋盘（会被原地修改）
     * @return 数独可解返回true，不可解返回false
     */
    bool solve(vector<vector<char>>& board){
        // 遍历数独棋盘的每一个位置（行优先遍历）
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                // 找到空位置（用.表示未填充）
                if(board[i][j] == '.'){
                    // 尝试填入'1'到'9'的每一个数字
                    for(char c = '1'; c <= '9'; c++){
                        // 先检查当前数字c填入(x,y)是否合法
                        if(isValid(board, i, j, c)){
                            // 1. 选择：填入合法数字c
                            board[i][j] = c;
                            // 2. 递归：基于当前填充状态，继续求解剩余空位置
                            // 如果递归返回true，说明后续所有空位置都已填满（数独解成），直接返回true
                            if(solve(board))
                                return true;
                            // 3. 回溯：如果递归返回false，说明当前填入的c不可行，恢复空位置（撤销选择）
                            board[i][j] = '.';
                        }
                    }
                    // 遍历完'1'-'9'都没有合法数字，说明当前路径无解，返回false让上一层回溯
                    return false;
                }
            }
        }
        // 遍历完整个棋盘，没有空位置了（所有位置都已合法填充），数独解成，返回true
        return true;
    }

    /**
     * 数独求解入口函数
     * 调用solve函数启动递归回溯，原地修改board得到解
     * @param board 待求解的数独棋盘（输入输出参数，解会直接写入）
     */
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
};

// 法二
// 优化1
// 最少选择优先（减少递归分支）
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<int> rowMask(9, 0);
        vector<int> colMask(9, 0);
        vector<int> boxMask(9, 0);

        // 初始化掩码（同基础优化）
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    int boxIdx = (i / 3) * 3 + (j / 3);
                    rowMask[i] |= (1 << num);
                    colMask[j] |= (1 << num);
                    boxMask[boxIdx] |= (1 << num);
                }
            }
        }

        backtrack(board, rowMask, colMask, boxMask);
    }

private:
    bool backtrack(vector<vector<char>>& board, vector<int>& rowMask, vector<int>& colMask, vector<int>& boxMask) {
        // 关键优化：找到可选数字最少的空位置（最少选择优先）
        pair<int, int> bestPos(-1, -1); // 最优空位置（i,j）
        int minOpts = 10; // 最少可选数字（最多9种，初始设为10）

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    int boxIdx = (i / 3) * 3 + (j / 3);
                    // 计算当前位置的可选数字数量：行+列+宫的已用数字合并，统计未用bit
                    int used = rowMask[i] | colMask[j] | boxMask[boxIdx];
                    int opts = 0;
                    for (int num = 1; num <= 9; ++num) {
                        if (!(used & (1 << num))) opts++;
                    }
                    // 更新最优位置（可选数更少）
                    if (opts < minOpts) {
                        minOpts = opts;
                        bestPos = {i, j};
                        // 可选数为1时直接跳出（无需再找更优位置）
                        if (minOpts == 1) break;
                    }
                }
            }
            if (minOpts == 1) break;
        }

        // 没有空位置，找到解
        if (bestPos.first == -1) return true;

        // 处理最优空位置（后续逻辑同基础优化）
        int i = bestPos.first, j = bestPos.second;
        int boxIdx = (i / 3) * 3 + (j / 3);
        for (int num = 1; num <= 9; ++num) {
            if (!(rowMask[i] & (1 << num)) && !(colMask[j] & (1 << num)) && !(boxMask[boxIdx] & (1 << num))) {
                // 选择数字
                board[i][j] = num + '0';
                rowMask[i] |= (1 << num);
                colMask[j] |= (1 << num);
                boxMask[boxIdx] |= (1 << num);

                // 递归求解
                if (backtrack(board, rowMask, colMask, boxMask)) {
                    return true;
                }

                // 回溯
                board[i][j] = '.';
                rowMask[i] &= ~(1 << num);
                colMask[j] &= ~(1 << num);
                boxMask[boxIdx] &= ~(1 << num);
            }
        }

        // 无合法数字，当前路径无解
        return false;
    }
};

// 法三
// 优化2
// 位掩码预存状态（核心优化）
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        // 位掩码：rowMask[i]的bit1~bit9表示第i行是否使用数字1~9（1=已用，0=可用）
        vector<int> rowMask(9, 0);
        vector<int> colMask(9, 0);
        // 3x3宫的索引：(i/3)*3 + (j/3)，对应0~8共9个宫
        vector<int> boxMask(9, 0);

        // 1. 初始化掩码：标记棋盘已存在的数字
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0'; // 字符转数字（1~9）
                    int boxIdx = (i / 3) * 3 + (j / 3); // 计算当前位置所属的3x3宫索引
                    // 标记对应bit为1（表示该数字已使用）
                    rowMask[i] |= (1 << num);
                    colMask[j] |= (1 << num);
                    boxMask[boxIdx] |= (1 << num);
                }
            }
        }

        // 2. 回溯求解（找到解后会直接修改board并返回）
        backtrack(board, rowMask, colMask, boxMask);
    }

private:
    // 回溯函数：返回是否找到有效解（找到则立即返回，避免冗余搜索）
    bool backtrack(vector<vector<char>>& board, vector<int>& rowMask, vector<int>& colMask, vector<int>& boxMask) {
        // 遍历棋盘，寻找空位置（.）
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    // 尝试填入1~9中未被使用的数字
                    for (int num = 1; num <= 9; ++num) {
                        int boxIdx = (i / 3) * 3 + (j / 3);
                        // 位运算判断数字是否可用：行/列/宫的对应bit均为0
                        bool isAvailable = !(rowMask[i] & (1 << num)) 
                                        && !(colMask[j] & (1 << num)) 
                                        && !(boxMask[boxIdx] & (1 << num));
                        
                        if (isAvailable) {
                            // 步骤1：选择数字，更新棋盘和掩码
                            board[i][j] = num + '0'; // 数字转字符
                            rowMask[i] |= (1 << num); // 标记数字已用
                            colMask[j] |= (1 << num);
                            boxMask[boxIdx] |= (1 << num);

                            // 步骤2：递归探索下一个空位置，找到解则直接返回
                            if (backtrack(board, rowMask, colMask, boxMask)) {
                                return true;
                            }

                            // 步骤3：回溯，撤销选择（恢复棋盘和掩码）
                            board[i][j] = '.';
                            rowMask[i] &= ~(1 << num); // 对应bit清0（取消标记）
                            colMask[j] &= ~(1 << num);
                            boxMask[boxIdx] &= ~(1 << num);
                        }
                    }
                    // 遍历完1~9均无合法数字，当前路径无解，返回false触发回溯
                    return false;
                }
            }
        }
        // 所有位置均填满，找到唯一解，返回true
        return true;
    }
};

// 法四
// 优化3
//  状态预存：用数组记录数字存在性（O (1) 合法性判断）| 最少候选数优先：优先处理 “选择最少” 的空格（减少回溯分支）  |  预处理空格位置：避免重复遍历棋盘
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        // 状态记录数组：标记行、列、3x3宫格中已出现的数字
        bool row_has[9][9]{};  // row_has[i][x]：第i行是否有数字x+1（x∈0-8）
        bool col_has[9][9]{};  // col_has[j][x]：第j列是否有数字x+1
        bool sub_box_has[3][3][9]{};  // sub_box_has[i'][j'][x]：(i',j')宫是否有数字x+1
        vector<pair<int, int>> empty_pos;  // 存储所有空格坐标

        // 初始化：记录已有数字状态和空格位置
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char b = board[i][j];
                if (b == '.') {
                    empty_pos.emplace_back(i, j);
                } else {
                    int x = b - '1';  // '1'-'9'转0-8（适配数组索引）
                    row_has[i][x] = col_has[j][x] = sub_box_has[i/3][j/3][x] = true;
                }
            }
        }

        // 计算空格(i,j)的候选数字数量
        auto get_candidates = [&](int i, int j) -> int {
            int cnt = 9;
            for (int x = 0; x < 9; x++) {
                if (row_has[i][x] || col_has[j][x] || sub_box_has[i/3][j/3][x]) {
                    cnt--;
                }
            }
            return cnt;
        };

        // 优先队列（最小堆）：按候选数从小到大存储空格（候选数, 行, 列）
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> empty_pq;
        for (auto& pos : empty_pos) {
            int i = pos.first, j = pos.second;
            empty_pq.emplace(get_candidates(i, j), i, j);
        }

        // 关键修复：用std::function声明递归函数类型（兼容C++11/C++17）
        // 先声明函数对象，再赋值lambda（避免“auto变量自引用”问题）
        function<bool()> dfs;
        dfs = [&]() -> bool {
            if (empty_pq.empty()) {  // 所有空格填充完成，返回成功
                return true;
            }

            // 取出候选数最少的空格（结构化绑定是C++17特性，若不支持可改用std::get）
            auto [_, i, j] = empty_pq.top();
            empty_pq.pop();

            int valid_candidates = 0;  // 记录实际有效候选数（回溯时更新队列）
            for (int x = 0; x < 9; x++) {
                // 跳过已存在的数字
                if (row_has[i][x] || col_has[j][x] || sub_box_has[i/3][j/3][x]) {
                    continue;
                }

                // 选择数字x+1填入空格
                board[i][j] = '1' + x;
                // 标记状态
                row_has[i][x] = col_has[j][x] = sub_box_has[i/3][j/3][x] = true;

                // 递归求解（调用已赋值的dfs）
                if (dfs()) {
                    return true;
                }

                // 回溯：撤销状态标记
                row_has[i][x] = col_has[j][x] = sub_box_has[i/3][j/3][x] = false;
                valid_candidates++;  // 统计有效候选数
            }

            // 回溯：当前空格无解，重新入队（更新候选数）
            empty_pq.emplace(valid_candidates, i, j);
            return false;
        };

        // 启动递归
        dfs();
    }
};